import heapq

# 超时
# class Solution(object):
#     def minmaxGasDist(self, stations, k):
#         """
#         :type stations: List[int]
#         :type k: int
#         :rtype: float
#         """
#         n = len(stations)
#         d = {i: 1 for i in range(n - 1)}
#         dist = [(stations[i] - stations[i + 1], i) for i in range(n - 1)]
#         heapq.heapify(dist)
#         for i in range(k):
#             node = heapq.heappop(dist)
#             d[node[1]] += 1
#             new_node = ((stations[node[1]] - stations[node[1] + 1]) / d[node[1]], node[1])
#             heapq.heappush(dist, new_node)
#         return - dist[0][0]

# 超时
# class Solution(object):
#     def minmaxGasDist(self, stations, k):
#         """
#         :type stations: List[int]
#         :type k: int
#         :rtype: float
#         """
#         n = len(stations)
#         d = {i: 1 for i in range(n - 1)}
#         prim = [stations[i] - stations[i + 1] for i in range(n - 1)]
#         dist = [(stations[i] - stations[i + 1], i) for i in range(n - 1)]
#         heapq.heapify(dist)
#         i = 0
#         while i < k:
#             now_node = heapq.heappop(dist)
#             now_dist = prim[now_node[1]]
#             next_dist = dist[0][0]
#             now_k = now_dist // next_dist + 1
#             add_k = max(now_k - d[now_node[1]], 1)
#             now_k = add_k + d[now_node[1]]
#             if i + add_k <= k:
#                 d[now_node[1]] = now_k
#                 new_node = (now_dist / now_k, now_node[1])
#                 i = i + add_k
#             else:
#                 d[now_node[1]] = d[now_node[1]] + k - i
#                 i = k
#                 new_node = (now_dist / d[now_node[1]], now_node[1])
#             heapq.heappush(dist, new_node)
#         return - dist[0][0]
# 二分搜索
class Solution(object):
    def minmaxGasDist(self, stations, k):
        """
        :type stations: List[int]
        :type k: int
        :rtype: float
        """
        n = len(stations)
        dist = [stations[i + 1] - stations[i] for i in range(n - 1)]
        max_D = max(dist)
        min_D = 0
        while max_D - min_D > 10**(-6):
            D = (max_D + min_D) / 2
            count = 0
            temp_max = -1
            flag = True
            for i in range(n - 1):
                if dist[i] > D:
                    if i < n - 2:
                        now_k = int(dist[i] / D) + 1
                        count += (now_k - 1)
                        if count > k:
                            flag = False
                            break
                        temp_max = max(temp_max, dist[i] / now_k)
                    else:
                        now_k = int(dist[i] / D) + 1
                        count += (now_k - 1)
                        if count > k:
                            flag = False
                            break
                        now_k += (k - count)
                        temp_max = max(temp_max, dist[i] / now_k)
                else:
                    temp_max = max(temp_max, dist[i])
            if not flag:
                min_D = D
            else:
                max_D = temp_max
        return max_D


data = Solution()
stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 9
print(data.minmaxGasDist(stations, k))
stations = [23, 24, 36, 39, 46, 56, 57, 65, 84, 98]
k = 1
print(data.minmaxGasDist(stations, k))
stations = [23, 24, 36, 39, 46, 56, 57, 65, 84, 98]
k = 900
print(data.minmaxGasDist(stations, k))
